package com.jjlin.chapter_3;
import java.util.*;
public class CD171{
    //二叉树节点
    public static class Node{
        public int val;
        public Node left;
        public Node right;
        public Node(int data){
            this.val = data;
        }
    }

    //建立二叉树
    public static Node createNodeList(int[][] nums, int root){
        if(nums == null || nums.length == 0 || nums[0] == null || nums[0].length == 0)
            return null;
        HashMap<Integer, Node> map = new HashMap<>();
        for(int i = 0; i < nums.length; ++i){
            map.putIfAbsent(nums[i][0], new Node(nums[i][0]));
            if(nums[i][1] != 0){
                map.putIfAbsent(nums[i][1], new Node(nums[i][1]));
                map.get(nums[i][0]).left = map.get(nums[i][1]);
            }
            if(nums[i][2] != 0){
                map.putIfAbsent(nums[i][2], new Node(nums[i][2]));
                map.get(nums[i][0]).right = map.get(nums[i][2]);
            }
        }
        return map.get(root);
    }

    //方法1：判断t1树中是否有与t2树拓扑结构完全相同的子树,时间复杂度为O(N * M)，其中N、M分别为二叉树t1和t2的节点数
    public static boolean isSubTree1(Node t1, Node t2){
        boolean flag = check(t1, t2);
        if(flag)
            return true;
        if(t1 != null)
            return isSubTree1(t1.left, t2) || isSubTree1(t1.right, t2);
        return false;
    }

    //递归地对t1和t2进行检查
    public static boolean check(Node t1, Node t2){
        if(t1 == null && t2 == null)
            return true;
        if((t1 == null && t2 != null) || (t1 != null && t2 == null))
            return false;
        if(t1.val != t2.val)
            return false;
        return check(t1.left, t2.left) && check(t1.right, t2.right);
    }

    //方法2：判断t1树中是否有与t2树拓扑结构完全相同的子树,时间复杂度为O(N + M)，其中N、M分别为二叉树t1和t2的节点数
    public static boolean isSubTree2(Node t1, Node t2){
        String str1 = serialByPre(t1);
        String str2 = serialByPre(t2);
        return getIndexOf(str1, str2) != -1;
    }

    //按先序遍历序列化二叉树
    public static String serialByPre(Node head){
        if(head == null)
            return "";
        StringBuilder sb = new StringBuilder();
        Stack<Node> stack = new Stack<>();
        stack.push(head);
        while(!stack.isEmpty()){
            Node cur = stack.pop();
            sb.append(cur != null ? (cur.val + "!") : "#!");
            if(cur != null){
                stack.push(cur.right);
                stack.push(cur.left);
            }
        }
        return sb.toString();
    }

    //KMP算法，算出主串s和匹配串m是否匹配，如果匹配则返回s中匹配子串的位置，否则返回-1
    public static int getIndexOf(String s, String m){
        if(s == null || m == null || m.length() < 1 || m.length() > s.length())
            return -1;
        char[] ss = s.toCharArray();
        char[] mm = m.toCharArray();
        int[] next = getNextArr(mm);
        int si = 0;
        int mi = 0;
        while(si < ss.length && mi < mm.length){
            if(ss[si] == mm[mi]){
                si++;
                mi++;
            }else if(mi != 0){
                mi = next[mi];
            }else{
                si++;
            }
        }
        return mi == m.length() ? si - mi : -1;
    }

    //获得匹配串的next数组（next[i]表示str(0..i-1)的前缀和后缀最长匹配长度）
    public static int[] getNextArr(char[] str){
        if(str.length == 1)
            return new int[]{-1};
        int[] next = new int[str.length];
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int cn = 0;
        while(i < str.length){
            if(str[i - 1] == str[cn]){
                next[i++] = ++cn;//这里别忘了i++
            }else if(cn > 0){
                cn = next[cn];
            }else{
                next[i++] = 0;
            }
        }
        return next;
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int root = sc.nextInt();
        int[][] nums = new int[n][3];
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < 3; ++j)
                nums[i][j] = sc.nextInt();
        Node head1 = createNodeList(nums, root);
        n = sc.nextInt();
        root = sc.nextInt();
        nums = new int[n][3];
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < 3; ++j)
                nums[i][j] = sc.nextInt();
        Node head2 = createNodeList(nums, root);
        System.out.println(isSubTree2(head1, head2));
    }
}

